package leetcode

// https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
func searchRange(nums []int, target int) []int {
	h1, h2 := -1, -1
	left, right := 0, len(nums)-1
	mid := left + (right-left)/2
	for ; left <= right; mid = left + (right-left)/2 {
		if nums[mid] == target {
			if (mid > 0 && nums[mid-1] < target) || (mid == 0) {
				h1 = mid
				break
			}
		}
		if nums[mid] < target {
			left = mid + 1
		} else if nums[mid] >= target {
			right = mid - 1
		}
	}

	left, right = 0, len(nums)-1
	mid = left + (right-left)/2
	for ; left <= right; mid = left + (right-left)/2 {
		if nums[mid] == target {
			if (mid < len(nums)-1 && nums[mid+1] > target) || (mid == len(nums)-1) {
				h2 = mid
				break
			}
		}
		if nums[mid] <= target {
			left = mid + 1
		} else if nums[mid] > target {
			right = mid - 1
		}
	}
	return []int{h1, h2}
}
